package simple;

import sword.offer.common.TreeNode;

import java.util.*;

/**
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class BinaryTreePreorderTraversal {
    /**
     * 用迭代的方式完成，递归太简单了
     * 递归的过程其实就是入栈出栈的过程，所以我们需要定义一个栈
     * */
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            if (Objects.isNull(root)) {
                return Collections.emptyList();
            }
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> result = new ArrayList<>();
            stack.add(root);
            while (!stack.isEmpty()) {
                TreeNode curNode = stack.pop();
                result.add(curNode.val);
                if (Objects.nonNull(curNode.right)) {
                    stack.add(curNode.right);
                }
                if (Objects.nonNull(curNode.left)) {
                    stack.add(curNode.left);
                }
            }
            return result;
        }
    }
}
